package com.zjs.jianzhioffer;

/**
 * 描述
 *
 * @author zhu
 * @version 1.0
 * @date 2021/2/9 12:20
 */
public class BitmapSort {
    /**
     * 使用位图法进行排序
     * 找到最小值和最大值，申请位图数组，对应位赋值为1，最后依次输出。
     *
     * @param arr
     */
    public static void bitmapSort(int[] arr) {
        int max = arr[0];
        int min = max;
        for (int i : arr) {
            if (max < i) {
                max = i;
            }
            if (min > i) {
                min = i;
            }
        }
        System.out.println("最大最小元素分别为：" + max + " " + min);

        int[] bitArr = new int[max - min + 1];
        for (int i : arr) {
            int index = i - min;
            bitArr[index]++;
        }

        System.out.println("bitmap后的数组元素为：");
        for (int i : bitArr) {
            System.out.print(i + " ");
        }
        System.out.println();

        int index = 0;
        for (int i = 0; i < bitArr.length; i++) {
            while (bitArr[i] > 0) {
                arr[index] = i + min;
                index++;
                bitArr[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 7, -3, 0, 0, 6, 6, 9, -11};
        bitmapSort(arr);
        System.out.println("Bitmap排序后的结果：");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}